The present disclosure generally relates to the field of graph theory and, more particularly, to approximating a lowest cost subgraph within a graph.
A graph is a representation of a set of nodes connected by edges. Graphs may be utilized to model a variety of different real-life network design problems, such as Very Large Scale Integration (“VLSI”) wire routing, communications network design, and facility location analysis. For example, the nodes in the graph may represent network equipment, such as routers and switches, and the edges in the graph may represent network connections, such as the physical cable that connects the routers and switches.
A number of different graph problems are directed to determining optimal graphs or optimal subsets of graphs according to certain criteria. One common type of graph problem is known as the Steiner tree problem. The Steiner tree problem is commonly defined as follows: given a graph and a subset of nodes (also referred to as terminals) contained in the graph, determine a minimum weight tree that connects all of the terminals. Unlike a minimum spanning tree, which is similarly defined, the Steiner tree may include intermediate nodes and edges that are not in the given graph. In order to determine the minimum weight tree, each node and/or edge in the graph may be assigned a weight. For an edge-weighted Steiner tree, the minimum weight tree minimizes the total edge cost. For a node-weighted Steiner tree, the minimum weight tree minimizes the total node cost.
Planar graphs represent a particular class of graphs in which the edges do not cross. In scenarios where the edges represent underground cable or fiber, the edges are typically planar and rarely, if ever, cross. While a number of different solutions have been proposed for approximating node-weighted Steiner trees, these conventional solutions generally do not address planar graphs.